package crawler.web.other;

import java.util.Arrays;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;

/**
 * @author waynechen Feb 12, 2012 11:08:34 PM
 */
public class Subsequence {
	public static void main(String[] args) {
		Character[] s1 = new Character[] { 'a', 'b', 'c', 'b', 'd', 'a', 'b' };
		Character[] s2 = new Character[] { 'b', 'd', 'c', 'a', 'b', 'a' };
		List<Character> list = Subsequence.LCS(s1, s2);
		String str = Arrays.toString(list.toArray());
		System.out.println(str);
	}

	/**
	 * get the longest common subsequence<br>
	 * note: not the consequence subsequence
	 * 
	 * @author waynechen
	 * @param s1
	 * @param s2
	 * @return
	 */
	public static <E> List<E> LCS(E[] s1, E[] s2) {
		int i;
		int j;
		dynamicPackage pac = new dynamicPackage();
		LCSLength(s1, s2, pac);
		i = s1.length;
		j = s2.length;
		List<E> list = new LinkedList<E>();
		while (i != 0 && j != 0) {
			if (s1[i - 1].equals(s2[j - 1])) {
				list.add(s1[i - 1]);
				i--;
				j--;
			} else if (pac.num[i][j - 1] >= pac.num[i - 1][j]) {//if reduce s2 and num is still larger than reduce s1
				// then reduce s2
				j--;
			} else {
				i--;
			}
		}
		Collections.reverse(list);
		return list;
	}

	public static <E> int LCSLength(E[] s1, E[] s2) {
		return LCSLength(s1, s2, new dynamicPackage());
	}

	private static <E> int LCSLength(E[] s1, E[] s2, dynamicPackage pac) {
		// initials to zeros, A[i][j] , i for index of s1, j for index of s2.
		// num[i][j] stores the max subsequence's length of
		// subsequence of first i elements in s1 and subsequence of first j elements in s2,
		// i,j >= 0
		pac.num = new int[s1.length + 1][s2.length + 1];

		//dynamic programming
		int i = 0, j = 0;
		for (i = 1; i <= s1.length; i++) {
			for (j = 1; j <= s2.length; j++) {
				if (s1[i - 1].getClass().equals(s2[j - 1].getClass()))
					pac.num[i][j] = 1 + pac.num[i - 1][j - 1];
				else
					pac.num[i][j] = Math.max(pac.num[i - 1][j], pac.num[i][j - 1]);
			}
		}
		return pac.num[s1.length][s2.length];
	}

	private static class dynamicPackage {
		public int[][] num = new int[0][0];
	}
}
//
//
//
//
//
//
//
//
//